package com.example.exercises;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

public class Solutio354 {
    public int maxEnvelopes(int[][] envelopes) {

        int n = envelopes.length;
        if (n <= 0) {
            return 0;
        }
        int left = envelopes[0][0], right = envelopes[0][1];
        int count = 1;

        for (int i = 1; i < n; i++) {
            if (envelopes[i][0] > left && envelopes[i][1] > right) {
                left = envelopes[i][0];
                right = envelopes[i][1];
                count++;
            }
            if (envelopes[i][0] < left && envelopes[i][1] < right) {
                left = envelopes[i][0];
                right = envelopes[i][1];
                count++;
            }
        }
        return count;
    }
}


class A {
    // envelopes = [[w, h], [w, h]...]
    public static void main(String[] args) {
        int[][] envelopes = {{2, 1}, {2, 3}, {2, 2}, {3, 4}, {4, 4}, {5, 5}};
        A a = new A();
        System.out.println(a.maxEnvelopes(envelopes));
    }

    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        System.out.println("---------" + envelopes[0].length);
        // 按宽度升序排列，如果宽度一样，则按高度降序排列
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            }
        });
        // 对高度数组寻找 LIS
        int[] height = new int[n];
        for (int i = 0; i < n; i++)
            height[i] = envelopes[i][1];
        return lengthOfLIS(height);
    }

    /* 返回 nums 中 LIS 的长度 */
    public int lengthOfLIS(int[] nums) {
        int piles = 0, n = nums.length;
        int[] top = new int[n];
        for (int i = 0; i < n; i++) {
            // 要处理的扑克牌
            int poker = nums[i];
            int left = 0, right = piles;
            // 二分查找插入位置
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] >= poker)
                    right = mid;
                else
                    left = mid + 1;
            }
            if (left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }
}

class suijishu {
    //    奖品数量
    static int i = 10;//一等奖
    static int i1 = 10;//二等奖
    static int i2 = 10;//三等奖


    public static void main(String[] args) {
        Random random = new Random();
//设置了循环，中一次一等奖就跳出循环停止
        while (i > 9) {
            double a = Math.random() * 1;
            System.out.println("a:" + a);
//            概率0.1
            if (a <= 0.1) {

                System.out.println("一等奖");
//                中一次减一个
                i = i - 1;
//                一等奖还剩i个
                System.out.println(i);

//                中一等奖后停止循环
//                break;

//            概率0.3
            } else if ((a <= 0.4) && (0.1 < a)) {
                if (i1 > 0) {
                    System.out.println("二等奖");
                    i1 = i1 - 1;
                    System.out.println(i1);
                }


//             概率0.6
            } else if ((0.4 < a) && (a <= 1)) {
                if (i2 > 0) {
                    System.out.println("三等奖");
                    i2 = i2 - 1;
                    System.out.println(i2);
                }
            }
        }

    }
}


class TEST {
    public static void main(String[] args) {
        double a = Math.random();
        double i = 1;
        if (a < 0.3) {
            System.out.println(true);
        } else {
            System.out.println(false);
        }
    }
}


